Thực đơn
Phân_tích_thuật_toán
Phân tích thời gian chạy là một phân loại lý thuyết ước tính và dự đoán sự gia tăng thời gian chạy của thuật toán khi kích thước đầu vào của nó (thường được ký hiệu là n) tăng. Hiệu quả thời gian chạy là một chủ đề rất được quan tâm trong khoa học máy tính: Một chương trình có thể mất vài giây, vài giờ hoặc thậm chí nhiều năm để hoàn thành việc thực thi, tùy thuộc vào thuật toán mà nó thực hiện. Mặc dù các kỹ thuật phân tích phần mềm có thể được sử dụng để đo thời gian chạy của thuật toán trong thực tế, chúng không thể cung cấp dữ liệu thời gian cho tất cả đầu vào có thể; cái sau chỉ có thể đạt được bằng các phương pháp lý thuyết của phân tích thời gian chạy.
Do các thuật toán độc lập với nền tảng (nghĩa là một thuật toán nhất định có thể được thực hiện bằng ngôn ngữ lập trình tùy ý trên một máy tính tùy ý chạy hệ điều hành tùy ý), có một số hạn chế đáng kể khi sử dụng phương pháp thực nghiệm để đánh giá hiệu năng so sánh của một tập hợp thuật toán.
Lấy ví dụ một chương trình tìm kiếm một mục cụ thể trong danh sách được sắp xếp có kích thước n. Giả sử chương trình này được triển khai trên Máy tính A, một máy hiện đại, sử dụng thuật toán tìm kiếm tuần tự và trên Máy tính B, một máy chậm hơn nhiều, sử dụng thuật toán tìm kiếm nhị phân. Kiểm tra điểm chuẩn trên hai máy tính chạy chương trình tương ứng của chúng có thể trông giống như sau:
| n (kích thước danh sách) | Thời gian chạy ở máy A (tính bằng nano giây) | Thời gian chạy ở máy tính B (tính bằng nano giây) |
|---|---|---|
| 16 | 8 | 100.000 |
| 63 | 32 | 150.000 |
| 250 | 125 | 200.000 |
| 1.000 | 500 | 250.000 |
Dựa trên các số liệu này, có thể dễ dàng đi đến kết luận rằng Máy tính A đang chạy một thuật toán có hiệu quả vượt trội so với Máy tính B. Tuy nhiên, nếu kích thước của danh sách đầu vào được tăng lên đủ lớn, kết luận đó được chứng minh là sai:
| n (kích thước danh sách) | Thời gian chạy ở máy A (tính bằng nano giây) | Thời gian chạy ở máy tính B (tính bằng nano giây) |
|---|---|---|
| 16 | 8 | 100.000 |
| 63 | 32 | 150.000 |
| 250 | 125 | 200.000 |
| 1.000 | 500 | 250.000 |
| ... | ... | ... |
| 1.000.000 | 500.000 | 500.000 |
| 4.000.000 | 2.000.000 | 550.000 |
| 16.000.000 | 8.000.000 | 600.000 |
| ... | ... | ... |
| 63,072 × 10 12 | 31,536 × 10 12 ns, </br> hoặc 1 năm | 1.375.000 ns, </br> hoặc 1,375 mili giây |
Máy tính A, chạy chương trình tìm kiếm tuần tự, thể hiện tốc độ tăng trưởng tuyến tính. Thời gian chạy của chương trình tỷ lệ thuận với kích thước đầu vào của nó. Nhân đôi kích thước đầu vào nhân đôi thời gian chạy, tăng gấp bốn lần kích thước đầu vào tăng gấp bốn lần thời gian chạy, v.v. Mặt khác, Computer B, chạy chương trình tìm kiếm nhị phân, thể hiện tốc độ tăng trưởng logarit. Tăng gấp bốn lần kích thước đầu vào chỉ làm tăng thời gian chạy thêm một lượng không đổi (trong ví dụ này là 50.000 ns). Mặc dù Máy tính A rõ ràng là một máy nhanh hơn, Máy tính B chắc chắn sẽ vượt qua Máy tính A trong thời gian chạy vì nó chạy một thuật toán với tốc độ tăng trưởng chậm hơn nhiều.
Một cách không chính thức, một thuật toán có thể được cho là thể hiện tốc độ tăng trưởng theo cấp độ của một hàm toán học nếu vượt quá một kích thước đầu vào n, hàm f ( n ) {\displaystyle f(n)} nhân một hằng số dương cung cấp giới hạn trên hoặc giới hạn cho thời gian chạy của thuật toán đó. Nói cách khác, với kích thước đầu vào đã cho n lớn hơn một số n 0 và hằng số c, thời gian chạy của thuật toán đó sẽ không bao giờ lớn hơn c × f ( n ) {\displaystyle c\times f(n)} . Khái niệm này thường được thể hiện bằng cách sử dụng ký hiệu Big O. Ví dụ, do thời gian chạy của sắp xếp chèn tăng theo phương trình bậc hai khi kích thước đầu vào của nó tăng lên, nên sắp xếp chèn là theo thứ tự O (n 2).
Ký hiệu Big O là một cách thuận tiện để diễn tả trường hợp xấu nhất cho một thuật toán nhất định, mặc dù nó cũng có thể được sử dụng để diễn tả trường hợp trung bình — ví dụ: trường hợp xấu nhất cho quicksort là O (n 2), nhưng thời gian chạy trường hợp trung bình là O(n log n).
Giả sử thời gian thực hiện theo quy tắc công suất, t ≈ k na, có thể tìm thấy hệ số a [8] bằng cách thực hiện các phép đo thực nghiệm về thời gian chạy { t 1 , t 2 } {\displaystyle \{t_{1},t_{2}\}} tại một số điểm kích thước vấn đề { n 1 , n 2 } {\displaystyle \{n_{1},n_{2}\}} và tính toán t 2 / t 1 = ( n 2 / n 1 ) a {\displaystyle t_{2}/t_{1}=(n_{2}/n_{1})^{a}} vậy a = log ( t 2 / t 1 ) / log ( n 2 / n 1 ) {\displaystyle a=\log(t_{2}/t_{1})/\log(n_{2}/n_{1})} . Nói cách khác, điều này đo độ dốc của đường thực nghiệm trên biểu đồ log log của thời gian thực hiện so với kích thước bài toán, tại một số điểm kích thước. Nếu thứ tự tăng trưởng thực sự tuân theo quy tắc sức mạnh (và do đó, đường trên log log log thực sự là một đường thẳng), giá trị thực nghiệm của a sẽ không đổi ở các phạm vi khác nhau, và nếu không, nó sẽ thay đổi (và đường là một đường cong) - nhưng vẫn có thể phục vụ cho việc so sánh bất kỳ hai thuật toán đã cho nào về các cấp độ hành vi tăng trưởng theo kinh nghiệm của chúng. Áp dụng cho bảng trên:
| n (kích thước danh sách) | Thời gian chạy của máy A (tính bằng nano giây) | Cấp độ địa phương của tăng trưởng (n ^ _) | Thời gian chạy máy tính B (tính bằng nano giây) | Cấp độ địa phương của tăng trưởng (n ^ _) |
|---|---|---|---|---|
| 15 | 7 | 100.000 | ||
| 65 | 32 | 1,04 | 150.000 | 0,28 |
| 250 | 125 | 1,01 | 200.000 | 0,21 |
| 1.000 | 500 | 1,00 | 250.000 | 0,16 |
| ... | ... | ... | ||
| 1.000.000 | 500.000 | 1,00 | 500.000 | 0,10 |
| 4.000.000 | 2.000.000 | 1,00 | 550.000 | 0,07 |
| 16.000.000 | 8.000.000 | 1,00 | 600.000 | 0,06 |
| ... | ... | ... |
Rõ ràng là thuật toán đầu tiên thể hiện một trật tự tăng trưởng tuyến tính thực sự tuân theo quy tắc sức mạnh. Các giá trị thực nghiệm cho cái thứ hai đang giảm đi nhanh chóng, cho thấy nó tuân theo một quy luật tăng trưởng khác và trong mọi trường hợp có thứ tự tăng trưởng địa phương thấp hơn nhiều (và cải thiện hơn nữa), theo kinh nghiệm, so với cái đầu tiên.
Độ phức tạp thời gian chạy cho kịch bản trường hợp xấu nhất của thuật toán đã cho đôi khi có thể được đánh giá bằng cách kiểm tra cấu trúc của thuật toán và đưa ra một số giả định đơn giản hóa. Hãy xem xét các mã giả sau đây:
1 get a positive integer from input2 if n > 103 print "Việc này có thể mất 1 lúc..."4 for i = 1 to n5 for j = 1 to i6 print i * j7 print "Xong!"
Một máy tính nhất định sẽ mất một lượng thời gian riêng biệt để thực hiện từng hướng dẫn liên quan đến việc thực hiện thuật toán này. Lượng thời gian cụ thể để thực hiện một lệnh đã cho sẽ khác nhau tùy thuộc vào lệnh nào được thực thi và máy tính nào đang thực hiện lệnh đó, nhưng trên máy tính thông thường, lượng này sẽ mang tính quyết định.[9] Giả sử các hành động được thực hiện trong bước 1 được coi là tiêu tốn thời gian T 1, bước 2 sử dụng thời gian T 2, v.v.
Trong thuật toán trên, các bước 1, 2 và 7 sẽ chỉ được chạy một lần. Đối với đánh giá trường hợp xấu nhất, cần giả định rằng bước 3 cũng sẽ được chạy. Do đó, tổng thời gian để chạy các bước 1-3 và bước 7 là:
T 1 + T 2 + T 3 + T 7 . {\displaystyle T_{1}+T_{2}+T_{3}+T_{7}.\,}Các vòng lặp trong các bước 4, 5 và 6 là khó khăn hơn để đánh giá. Kiểm tra vòng lặp bên ngoài trong bước 4 sẽ thực hiện (n + 1) lần (lưu ý rằng cần thêm một bước để chấm dứt vòng lặp for, do đó n + 1 chứ không phải n thực thi), sẽ tiêu tốn thời gian T 4 (n + 1). Mặt khác, vòng lặp bên trong được điều chỉnh bởi giá trị của j, lặp từ 1 đến i. Trong lần đầu tiên đi qua vòng ngoài, j lặp từ 1 đến 1: Vòng lặp bên trong tạo một lượt, do đó, việc chạy thân vòng trong (bước 6) tiêu tốn thời gian T 6 và kiểm tra vòng lặp bên trong (bước 5) tiêu tốn 2 T 5 lần. Trong lần truyền tiếp theo qua vòng ngoài, j lặp từ 1 đến 2: vòng trong tạo ra hai lần, do đó, việc chạy thân vòng trong (bước 6) tiêu tốn 2 T 6 thời gian và kiểm tra vòng trong (bước 5) tiêu tốn 3 T 5 lần.
Nhìn chung, tổng thời gian cần thiết để chạy phần thân vòng trong có thể được biểu diễn dưới dạng một tiến trình số học:
T 6 + 2 T 6 + 3 T 6 + ⋯ + ( n − 1 ) T 6 + n T 6 {\displaystyle T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}} T 6 [ 1 + 2 + 3 + ⋯ + ( n − 1 ) + n ] = T 6 [ 1 2 ( n 2 + n ) ] {\displaystyle T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2}}(n^{2}+n)\right]}Tổng thời gian cần thiết để chạy thử nghiệm vòng lặp bên ngoài có thể được đánh giá tương tự:
2 T 5 + 3 T 5 + 4 T 5 + ⋯ + ( n − 1 ) T 5 + n T 5 + ( n + 1 ) T 5 = T 5 + 2 T 5 + 3 T 5 + 4 T 5 + ⋯ + ( n − 1 ) T 5 + n T 5 + ( n + 1 ) T 5 − T 5 {\displaystyle {\begin{aligned}&2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}\\=\ &T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}\end{aligned}}}có thể được coi là
T 5 [ 1 + 2 + 3 + ⋯ + ( n − 1 ) + n + ( n + 1 ) ] − T 5 = [ 1 2 ( n 2 + n ) ] T 5 + ( n + 1 ) T 5 − T 5 = T 5 [ 1 2 ( n 2 + n ) ] + n T 5 = [ 1 2 ( n 2 + 3 n ) ] T 5 {\displaystyle {\begin{aligned}&T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}\\=&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}\\=&T_{5}\left[{\frac {1}{2}}(n^{2}+n)\right]+nT_{5}\\=&\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}\end{aligned}}}Do đó, tổng thời gian chạy cho thuật toán này là:
f ( n ) = T 1 + T 2 + T 3 + T 7 + ( n + 1 ) T 4 + [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 {\displaystyle f(n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}}làm giảm
f ( n ) = [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 {\displaystyle f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}}Theo nguyên tắc thông thường, người ta có thể giả định rằng thành phần bậc cao nhất trong bất kỳ hàm đã cho nào chi phối tốc độ tăng trưởng của nó và do đó xác định thứ tự thời gian chạy của nó. Trong ví dụ này, n 2 là số hạng bậc cao nhất, vì vậy người ta có thể kết luận rằng f (n) = O (n 2). Chính thức điều này có thể được chứng minh như sau:
Prove that [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ c n 2 , n ≥ n 0 {\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}}
[ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ ( n 2 + n ) T 6 + ( n 2 + 3 n ) T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ( for n ≥ 0 ) {\displaystyle {\begin{aligned}&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\\\leq &(n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ ({\text{for }}n\geq 0)\end{aligned}}}
Let k be a constant greater than or equal to [T1..T7]
T 6 ( n 2 + n ) + T 5 ( n 2 + 3 n ) + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ k ( n 2 + n ) + k ( n 2 + 3 n ) + k n + 5 k = 2 k n 2 + 5 k n + 5 k ≤ 2 k n 2 + 5 k n 2 + 5 k n 2 ( for n ≥ 1 ) = 12 k n 2 {\displaystyle {\begin{aligned}&T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k\\=&2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\ ({\text{for }}n\geq 1)=12kn^{2}\end{aligned}}}
Therefore [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ c n 2 , n ≥ n 0 for c = 12 k , n 0 = 1 {\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1}
Một cách tiếp cận thanh lịch hơn để phân tích thuật toán này sẽ là tuyên bố rằng [ T 1.. T 7 ] đều bằng một đơn vị thời gian, trong một hệ thống các đơn vị được chọn sao cho một đơn vị lớn hơn hoặc bằng thời gian thực tế cho các bước này. Điều này có nghĩa là thời gian chạy của thuật toán bị hỏng như sau:[11]
4 + ∑ i = 1 n i ≤ 4 + ∑ i = 1 n n = 4 + n 2 ≤ 5 n 2 ( for n ≥ 1 ) = O ( n 2 ) . {\displaystyle 4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\ ({\text{for }}n\geq 1)=O(n^{2}).}
Phương pháp phân tích thời gian chạy cũng có thể được sử dụng để dự đoán tốc độ tăng trưởng khác, chẳng hạn như tiêu thụ không gian bộ nhớ. Ví dụ, xem xét mã giả sau đây quản lý và phân bổ lại mức sử dụng bộ nhớ theo chương trình dựa trên kích thước của tệp mà chương trình đó quản lý:
while (file vẫn mở) let n = kích thước của tệp for mỗi 100.000 kilobyte gia tăng kích thước tập tin nhân đôi số lượng bộ nhớ dự trữ
Trong trường hợp này, khi kích thước tệp n tăng, bộ nhớ sẽ được tiêu thụ với tốc độ tăng trưởng theo cấp số nhân, theo thứ tự O (2 n). Đây là tốc độ tăng trưởng cực kỳ nhanh và rất có thể không thể kiểm soát được đối với việc tiêu thụ tài nguyên bộ nhớ.
Thực đơn
Phân_tích_thuật_toánLiên quan
Tài liệu tham khảo
WikiPedia: Phân_tích_thuật_toán